#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
vector<long long> h(100010, 0);
long long e = 1;
unordered_map<long long, long long> kh, hk;
void heap_swap(long long i, long long j)
{
    swap(kh[hk[i]], kh[hk[j]]);
    swap(hk[i], hk[j]);
    swap(h[i], h[j]);
}
void up(long long i)
{
    long long p = i / 2;
    if (p && h[p] > h[i])
    {
        heap_swap(p, i);
        up(p);
    }
}
void down(long long i)
{
    long long low = i;
    long long l = i * 2, r = i * 2 + 1;
    if (l < e && h[l] < h[low])
        low = l;
    if (r < e && h[r] < h[low])
        low = r;
    if (low != i)
    {
        heap_swap(low, i);
        down(low);
    }
}
void rm(long long i)
{
    long long last = e - 1;
    heap_swap(last, i);
    e--;
    down(i), up(i);
}
void modi(long long i, long long x)
{
    h[i] = x;
    up(i), down(i);
}
int main()
{
    long long m;
    cin >> m;
    while (m--)
    {
        string op;
        cin >> op;
        if (op == "I")
        {
            static long long k = 1;
            long long temp;
            cin >> temp;
            h[e] = temp;
            kh[k] = e, hk[e] = k;
            ++e, ++k;
            up(e - 1);
        }
        else if (op == "PM")
        {
            cout << h[1] << endl;
        }

        else if (op == "DM")
        {
            rm(1);
        }
        else if (op == "D")
        {
            long long k;
            cin >> k;
            rm(kh[k]);
        }
        else if (op == "C")
        {
            long long k, x;
            cin >> k >> x;
            modi(kh[k], x);
        }
    }
    return 0;
}